Minimum partition of an independence system into independent sets

Abstract

Given an independence system (E, P), the Minimum Partition Problem (MPP) seeks a partition of E into the least number of independent sets. This notion provides a unifying framework for a number of combinatorial optimisation problems, including various conditional colouring problems for graphs. The smallest integer n such that E can be partitioned into n independent sets is called the P-chromatic number of E. In this article we study MPP and the P-chromatic number with emphasis on connections with a few other well-studied optimisation problems. In particular, we show that the P-chromatic number of E is equal to the domination number of a split graph associated with (E, P). With the help of th..